home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / ICON_8 / BENCH_FO / QUEENS.ICN < prev    next >
Text File  |  1990-04-06  |  3KB  |  105 lines
  1. ############################################################################
  2. #
  3. #    Name:    queens.icn
  4. #
  5. #    Title:    Generate solutions to the n-queens problem
  6. #
  7. #    Author:    Stephen B. Wampler
  8. #
  9. #    Date:    June 10, 1988
  10. #
  11. ############################################################################
  12. #  
  13. #     This program displays the solutions to the non-attacking n-
  14. #  queens problem: the ways in which n queens can be placed on an
  15. #  n-by-n chessboard so that no queen can attack another. A positive
  16. #  integer can be given as a command line argument to specify the
  17. #  number of queens. For example,
  18. #  
  19. #          iconx queens -n8
  20. #  
  21. #  displays the solutions for 8 queens on an 8-by-8 chessboard.  The
  22. #  default value in the absence of an argument is 6.  One solution
  23. #  for six queens is:
  24. #  
  25. #         -------------------------
  26. #         |   | Q |   |   |   |   |
  27. #         -------------------------
  28. #         |   |   |   | Q |   |   |
  29. #         -------------------------
  30. #         |   |   |   |   |   | Q |
  31. #         -------------------------
  32. #         | Q |   |   |   |   |   |
  33. #         -------------------------
  34. #         |   |   | Q |   |   |   |
  35. #         -------------------------
  36. #         |   |   |   |   | Q |   |
  37. #         -------------------------
  38. #  
  39. #  Comments: There are many approaches to programming solutions to
  40. #  the n-queens problem.  This program is worth reading for
  41. #  its programming techniques.
  42. #  
  43. ############################################################################
  44. #
  45. #  Links: options, post
  46. #
  47. ############################################################################
  48.  
  49. link options, post
  50.  
  51. global n, solution
  52.  
  53. procedure main(args)
  54.    local i, opts
  55.  
  56.    Init__()
  57.  
  58.    opts := options(args,"n+")
  59.    n := \opts["n"] | 6
  60.    if n <= 0 then stop("-n needs a positive numeric parameter")
  61.  
  62.    solution := list(n)        # ... and a list of column solutions
  63.    write(n,"-Queens:")
  64.    every q(1)            # start by placing queen in first column
  65.  
  66.    Term__()
  67.  
  68. end
  69.  
  70. # q(c) - place a queen in column c.
  71. #
  72. procedure q(c)
  73.    local r
  74.    static up, down, rows
  75.    initial {
  76.       up := list(2*n-1,0)
  77.       down := list(2*n-1,0)
  78.       rows := list(n,0)
  79.       }
  80.    every 0 = rows[r := 1 to n] = up[n+r-c] = down[r+c-1] &
  81.       rows[r] <- up[n+r-c] <- down[r+c-1] <- 1        do {
  82.          solution[c] := r    # record placement.
  83.          if c = n then show()
  84.          else q(c + 1)        # try to place next queen.
  85.          }
  86. end
  87.  
  88. # show the solution on a chess board.
  89. #
  90. procedure show()
  91.    static count, line, border
  92.    initial {
  93.       count := 0
  94.       line := repl("|   ",n) || "|"
  95.       border := repl("----",n) || "-"
  96.       }
  97.    write("solution: ", count+:=1)
  98.    write("  ", border)
  99.    every line[4*(!solution - 1) + 3] <- "Q" do {
  100.       write("  ", line)
  101.       write("  ", border)
  102.       }
  103.    write()
  104. end
  105.